//
// Created by ZYZ on 2020/6/10.
// 参考: https://cshihong.github.io/2017/09/28/%E7%BA%BF%E6%80%A7%E9%93%BE%E5%BC%8F%E8%A1%A8/
//
#include "redefinition_linked_list.h"
#include <stdlib.h>
#include <iostream>

using namespace std;

// 构造一个空的线性链表，只有一个空的头结点
Status InitList(LinkList &L) {
    Link p;
    p = (Link) malloc(sizeof(LNode)); // 生成头结点
    if (p) {
        p->next = NULL;
        L.head = L.tail = p;
        L.len = 0;
        return OK;
    } else
        return ERROR;//内存分配不够
}//InitList


// 分配一个值为e的结点，并且 p 指向该结点，若成功返回 OK；若分配失败。则返回 ERROR
Status MakeNode(Link &p, ElemType e) {
    p = (Link) malloc(sizeof(LNode));
    if (!p)
        return ERROR;
    p->data = e;
    return OK;
}//MakeNode

void FreeNode(Link &p) {
    // 释放p所指结点
    free(p);
    p = NULL;
}//FreeNode


//销毁线性链表L，L不再存在
//和 ClearList() 的区别就是 free(p);
Status DestroyList(LinkList &L) {

    for (; L.head != L.tail; L.len--) { //释放链表中结点所占的内存空间
        Link pt;
        pt = L.head;
        L.head = L.head->next;
        free(pt) ;
    }
    free(L.head);                       //这里 free 了但是 L.head 所指向的变量还在??
    if (L.len == 0) {                   //使L的头指针和尾指针不指向任何地方
        L.head = NULL;
        L.tail = NULL;
//        LinkList *p = &L;
//        free(p);
        return OK;
    } else {
        return ERROR;
    }
}


//将线性链表L重置为空表，并释放原链表的结点空间
Status ClearList(LinkList &L) {
    Link temp = L.head;
    L.head = L.head->next;
    for (; L.len > 0; L.len--) {//释放链表中的结点所占的内存空间
        Link pt;
        pt = L.head;
        L.head = L.head->next;
        free(pt);
    }
    L.head = temp;
    if (L.len == 0 && L.head == L.tail) {
        return OK;
    } else {
        return ERROR;
    }
}


//已知 h 指向线性链表的头结点，将 s 所指结点 插入在第一个节点之前 (这就是 First 的含义)
Status InsFirst(Link h, Link s) {
    if ((!s) && (!h->next))
        return ERROR;
    s->next = h->next;
    h->next = s;
    return OK;
}//InsFirst


//已知 h 指向线性链表的头结点，将 s 所指结点插入在第一个结点之前
Status InsFirst(LinkList &L, Link s) {
    s->next = L.head;
    L.head = s;
    L.len++;
    if (L.len == 1) {
        L.tail = s;
    }
    return OK;
}


//已知 h 指向线性链表的头结点，删除链表中的第一个结点并以 q 返回
Status DelFirst(Link h, Link &q) {
    q = h->next;
    h->next = h->next->next;
    return OK;
}


Position GetHead(LinkList L) {
    // 返回线性链表L中头结点的位置
    return L.head;
}//GetHead


//返回线性链表L中最后一个结点的位置
Position GetLast(LinkList L) {
    return L.tail;
}


//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置
//若无前驱，则返回 NULL
Position PriorPos(LinkList L, Link p) { //Prior : [ˈpraɪə(r)]  先前的
    Link temp = L.head;
    for (; temp->next != p && temp; temp = temp->next) {}
    if (temp->next == p) {
        return temp;
    } else return NULL;
}


Status SetCurElem(Link p, ElemType e) {
    // 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
    p->data = e;
    return OK;
}//SetCurElem


//已知 p 指向线性链表 L 中的一个结点，返回 p 所指结点的直接后继的位置，
//若无后继，则返回 NULL
Position NextPos(LinkList L, Link p) {
    Link temp = L.head->next;
    for (; temp != p->next && temp; temp = temp->next) {}
    if (temp == p->next) {
        return temp;
    } else return NULL;
}


//返回 p 指示线性链表 L 中第 i 个结点的位置并返回 OK，i 值不合法时返回 ERROR
Status LocatePos(LinkList L, int i, Link &p) {
    for (int j = 1; L.head && j <= i; j++, L.head = L.head->next) {}
    if (L.head) {
        p = L.head;
        return OK;
    } else return ERROR;
}


Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
    /* 返回线性链表L中第1个与e满足函数 compare() 判定关系的元素的位置， */
    /* 若不存在这样的元素，则返回NULL */
    Link p = L.head;
    do
        p = p->next;
    while (p && !(compare(p->data, e))); /* 没到表尾且没找到满足关系的元素 */
    return p;
}


Status ListInsert_L(LinkList &L, int i, ElemType e) {

    //在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e
    Link link_head;
    if (!LocatePos(L, i - 1, link_head))                     //获取 L 中第 i - 1 处的结点，并赋值给 link_head
        return ERROR;       //值不合法

    Link to_insert_link;
    if (!MakeNode(to_insert_link, e)) return ERROR;             //结点存储分配失败

    // 在 link_head 所指向的第 i - 1 个结点后插入 to_insert_link
    InsFirst(link_head, to_insert_link);                           //对于从第 i 个结点开始的链表，第 i-1 个结点是它的头结点

    return OK;
}//ListInsert_L


//合并 La、Lb 的内容到 Lc 中
Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, int (*compare)(ElemType, ElemType)) {

    //已知单链线性表 La 和 Lb 的元素按值非递减排列
    //归并 La 和 Lb 得到新的单链线性表 Lc, Lc 的元素也按值非递减排列
    if (!InitList(Lc))
        return ERROR; //存储空间分配失败

    Link ha = GetHead(La);                                          //返回线性链表 La 中头结点的位置赋值给 Link
    Link hb = GetHead(Lb);                                          //ha 和 hb 分别指向 La 和 Lb 的头结点
    Position pa = NextPos(La, ha);                                  //获取 La 中的头结点 ha 的下一个结点 pa
    Position pb = NextPos(Lb, hb);                                   //获取 Lb 中的头结点 hb 的下一个结点 pb

    while (pa && pb) {                                              //La 和 Lb 均非空

        ElemType a = GetCurElem(pa);                                //获取 pa 的 data 值赋值给 a
        ElemType b = GetCurElem(pb);                                //a 和 b 为两表中当前比较元素
        Link q;

        if ((*compare)(a, b) <= 0) {                                //如果 a 小于 b，则删除 a 中第一个元素并添加到 Lc 中
            DelFirst(ha, q);
            Append(Lc, q);
            pa = NextPos(La,
                         ha);                                   //因为 ha 之前的后边的那个结点被 DelFirst 删掉了，所以这里重新把 La 的头结点 ha 的下一个结点赋值给 pa
        } else {       // a > b
            DelFirst(hb, q);
            Append(Lc, q);
            pb = NextPos(Lb, hb);
        }
    }//while

    if (pa)                                                         //说明 pb 是空的，pa 不是空的
        Append(Lc, pa);                                         //链接 a 中剩余结点
    else
        Append(Lc, pb);                                         //链接 Lb 中剩余结点

    FreeNode(ha);
    FreeNode(hb);                                               //释放 La 和 Lb 的头结点

    return OK;
}


ElemType GetCurElem(Link p) {
    // 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
    return p->data;
}//GetCurElem


Status SetCurElem(Link &p, ElemType e) {
    //已知p指向线性链表L中的一个结点，用e更新p所指结点中数据元素的值
    p->data = e;
    return OK;
}


Status ListEmpty(LinkList L) {
    // 若线性链表L为空表，则返回TRUE，否则返回FALSE
    if (L.len)
        return ERROR;
    else
        return OK;
}//ListEmpty



//将指针s所指（彼此以指针相链）的一串结点链接在线性链表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点
Status Append(LinkList &L, Link s) {
    if (s) {
        Link temp = s;
        for (; s->next; s = s->next) {
            L.len++;
        }//让S移动到链表的最后一个结点
        L.len++;
        L.tail->next = temp;
        L.tail = s;//使L.tail指向最后一个结点
        return OK;
    } else return ERROR;
}


//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点
Status Remove(LinkList &L, Link &q) {
    if (L.head != L.tail) {
        q = L.tail;//用q返回尾结点
        Link temp;
        temp = L.head;
        for (; temp->next != L.tail; temp = temp->next) {}//使temp指向尾结点的前一个结点
        L.tail = temp;//使尾结点指向新的尾结点
        L.tail->next = NULL;
        free(temp->next);//删除旧的尾结点
        L.len--;
        return OK;
    } else return ERROR;
}


//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，
//并修改指针p指向新插入的结点
Status InsBefore(LinkList &L, Link &p, Link s) {
    Link temp = L.head;
    for (; temp->next != p && temp; temp = temp->next) {}
    if (temp->next == p) {
        s->next = p;
        temp->next = s;
        p = s;
        L.len++;
        return OK;
    } else return ERROR;
}


//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，
//并修改指针p指向新插入的结点
Status InsAfter(LinkList &L, Link &p, Link s) {
    Link temp = L.head;
    for (; temp != p && temp; temp = temp->next) {}
    if (temp == p) {
        temp->next = s;
        s->next = p;
        p = s;
        if (temp == L.tail)
            L.tail = s;
        L.len++;
        return OK;
    } else return ERROR;
}

Status ListTraverse(LinkList L, Status(*visit)(ElemType)) {
    /* 依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败 */
    Link p = L.head->next;
    int j;
    for (j = 1; j <= L.len; j++) {
        visit(p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}
